package arithmetic.LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 翻转字符
 * @author jiangfeng 2019/7/22 17:19
 *
 * 给定一个字符串，逐个翻转字符串中的每个单词。
 * 示例 1：
 *
 * 输入: "the sky is blue"
 * 输出: "blue is sky the"
 * 示例 2：
 *
 * 输入: "  hello world!  "
 * 输出: "world! hello"
 * 链接：https://leetcode-cn.com/problems/reverse-words-in-a-string
 */
public class ReverseWords {

    public static void main(String[] args) {
        ReverseWords instance = new ReverseWords();
        String test2= " hello  world haha! ";

        String test3=  "the sky is blue";
        System.out.println(instance.reverseWord3("hello world haha!"));
        System.out.println(instance.reverseWord3(test2));
         System.out.println(instance.reverseWord3(test3));
    }

    /**
     * 基本思路: 先翻转每个单词, 再做整体翻转
     * @param s
     */
    public String reverseWord(String s){
        //trim()是为了去掉前导或尾随空格
        //split():这是正则表达式。+表示至少1，所以在这种情况下，" +"意味着至少有一个空格
        String[] words = s.split(" +");
        //Arrays.asList()产生的list对象会使用底层数组作为其物理实现
        Collections.reverse(Arrays.asList(words));
        // 这个list的 Arrays的内部类,1.传入的值不能是基本数据类型的数据,2.不能新增删除元素,3.且改变list的元素位置,也会改变原数组的元素位置.
        return String.join(" ",words);
    }

    /**
     * 基本思路: 先翻转每个单词, 再做整体翻转
     * @return
     */
    public String reverseWord2(String s){
        char[] chars = s.toCharArray();

        int worldStart=0;
        for (int i = 0; i < chars.length; i++) {
            if(chars[i]==' '){
                reverseW(chars,worldStart,i-1);
                worldStart=i+1;
            }
        }
        reverseW(chars,worldStart,chars.length-1);// 最后一个

        replaceSpace(chars);
        // 全部换位置
        reverseW(chars,0,chars.length-1);

        return new String(chars);
    }

    /**
     * 执行翻转
     * @param chars
     * @param start
     * @param end
     */
    private void reverseW(char[] chars, int start, int end) {
        while (start < end) {
            char temp = chars[start];
            chars[start] = chars[end];
            chars[end] = temp;
            start++;
            end--;
        }
    }


    /**
     * 去掉字符区间中的空格
     * 重新读写内存即可
     * @param chars
     */
    private void replaceSpace(char[] chars) {
        int i = 0, j = 0, length = chars.length;
        while (i < length) {
            while (i < length && chars[i] == ' ') {
                i++;
            }
            while (i < length && chars[i] != ' ') {
                chars[j++] = chars[i++];
            }
            if (i < length && j>0) {
                chars[j++]=' ';//手动个 world以空格分开
            }
        }
        while (j<length){ // 删去最后的, 用空格
            chars[j++] = ' ';
        }
    }

    /**
     * 加去空格版,去空格和替换合体一次循环
     * @param s
     * @return
     */
    public String reverseWord3(String s) {
        char[] chars = s.toCharArray();
        int i = 0, j = 0, start = 0, n = chars.length; //i是读取指针, j是写指针
        while (i < n) {
            while (i < n && chars[i] == ' ') {
                i++;// 空格就接着读
            }
            if (i < n && j > 0) {
                chars[j++] = ' ';// 单词间加个空格, 一定要在下面那个while 之上否则会在最后多加一个空格
                start = j;
            }
            while (i < n && chars[i] != ' ') {
                chars[j++] = chars[i++];
            }
            reverseW(chars, start, j - 1);
            while (i < n && chars[i] == ' ') { // 结尾也去空
                i++;// 空格就接着读
            }
        }
        // reverseW(chars, start, j - 1);
        char[] chars1 = Arrays.copyOf(chars, j);
        // 全部换位置
        reverseW(chars1,0,chars1.length-1);
        return new String(chars1);
    }

}
